package com.wtgroup.demo.mianshi.算法.二叉树.遍历;

import com.wtgroup.demo.mianshi.算法.二叉树.model.CompleteBinTree;
import com.wtgroup.demo.mianshi.算法.二叉树.model.Node;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

/**
 * @author dafei
 * @version 0.1
 * @date 2021/3/27 20:29
 */
public class D_先序 {

    public static void main(String[] args) {
        List<Integer> vals = Arrays.asList(1,2,3,4,5,6,7,8);
        CompleteBinTree<Integer> binTree = new CompleteBinTree<Integer>(vals);

        Node<Integer> root = binTree.getRoot();

        // m1(root);
        // m2(root);
        m2_2(root);
    }

    /**
     * 递归
     * @param root
     */
    public static void m1(Node root, ArrayList<Node> result) {
        // System.out.print(root.getData() + " ");
        result.add(root);
        if (root.getLeft()!=null) {
            m1(root.getLeft(), result);
        }
        if (root.getRight() != null) {
            m1(root.getRight(), result);
        }
    }

    /**
     * Note: 叶子节点考虑其含有左右两个null节点有点用.
     * https://blog.csdn.net/My_Jobs/article/details/43451187
     * @param root
     */
    public static void m2_2(Node root) {
        Stack<Node> stack = new Stack<>();
        Node curNode = root;
        while (curNode !=null || !stack.isEmpty()) {
            if (curNode != null) {
                System.out.print(curNode.getData() + " ");
                stack.push(curNode);
                curNode = curNode.getLeft();
            } else {
                curNode = stack.pop().getRight();
            }

        }
    }

    /**
     * 栈
     *
     * 压栈是为了待会儿取其右树.
     *
     * @deprecated 虽然避免了空节点压栈出栈操作, 但逻辑复杂了.
     */
    public static void m2(Node root) {
        Stack<Node> stack = new Stack<>();
        Node curNode = root;
        while (curNode != null) {
            System.out.print(curNode.getData() + " ");
            // 左子节点不为空时, 才push
            if (curNode.getLeft() != null) {
                stack.push(curNode);
                curNode = curNode.getLeft();
            } else if(curNode.getRight() != null){
                curNode = curNode.getRight();
            } else {
                // 叶子节点: 弹栈, 取右子节点作为当前节点
                // 考虑弹出的父节点没有右子节点
                curNode = null; // 先清除, 最后死循环
                while (!stack.isEmpty() && (curNode = stack.pop().getRight()) == null) {}
            }
        }
    }

}
